

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>Discrete Transforms &mdash; CVXOPT User&#39;s Guide</title>
  

  
  
  
  

  
  <script type="text/javascript" src="_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
        <script src="_static/jquery.js"></script>
        <script src="_static/underscore.js"></script>
        <script src="_static/doctools.js"></script>
        <script src="_static/language_data.js"></script>
    
    <script type="text/javascript" src="_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="copyright" title="Copyright" href="copyright.html" />
    <link rel="next" title="Sparse Linear Equations" href="spsolvers.html" />
    <link rel="prev" title="The LAPACK Interface" href="lapack.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="index.html" class="icon icon-home"> CVXOPT User's Guide
          

          
          </a>

          
            
            
              <div class="version">
                1.2.5
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <ul class="current">
<li class="toctree-l1"><a class="reference internal" href="copyright.html">Copyright and License</a></li>
<li class="toctree-l1"><a class="reference internal" href="intro.html">Introduction</a></li>
<li class="toctree-l1"><a class="reference internal" href="matrices.html">Dense and Sparse Matrices</a></li>
<li class="toctree-l1"><a class="reference internal" href="blas.html">The BLAS Interface</a></li>
<li class="toctree-l1"><a class="reference internal" href="lapack.html">The LAPACK Interface</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Discrete Transforms</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#discrete-fourier-transform">Discrete Fourier Transform</a></li>
<li class="toctree-l2"><a class="reference internal" href="#discrete-cosine-transform">Discrete Cosine Transform</a></li>
<li class="toctree-l2"><a class="reference internal" href="#discrete-sine-transform">Discrete Sine Transform</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="spsolvers.html">Sparse Linear Equations</a></li>
<li class="toctree-l1"><a class="reference internal" href="coneprog.html">Cone Programming</a></li>
<li class="toctree-l1"><a class="reference internal" href="solvers.html">Nonlinear Convex Optimization</a></li>
<li class="toctree-l1"><a class="reference internal" href="modeling.html">Modeling</a></li>
<li class="toctree-l1"><a class="reference internal" href="c-api.html">C API</a></li>
<li class="toctree-l1"><a class="reference internal" href="printing.html">Matrix Formatting</a></li>
<li class="toctree-l1"><a class="reference external" href="http://cvxopt.org">cvxopt.org</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="index.html">CVXOPT User's Guide</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="index.html">Docs</a> &raquo;</li>
        
      <li>Discrete Transforms</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="discrete-transforms">
<span id="c-fftw"></span><h1>Discrete Transforms<a class="headerlink" href="#discrete-transforms" title="Permalink to this headline">¶</a></h1>
<p>The <code class="xref py py-mod docutils literal notranslate"><span class="pre">cvxopt.fftw</span></code> module is an interface to the FFTW library and
contains routines for discrete Fourier, cosine, and sine transforms.
This module is optional, and only installed when the FFTW library is made
available during the CVXOPT installation.</p>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<p><a class="reference external" href="http://www.fftw.org">FFTW3 code, documentation, copyright and license</a></p>
</div>
<div class="section" id="discrete-fourier-transform">
<h2>Discrete Fourier Transform<a class="headerlink" href="#discrete-fourier-transform" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.fftw.dft">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">dft</code><span class="sig-paren">(</span><em class="sig-param"><span class="n">X</span></em><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.dft" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense complex matrix with their discrete
Fourier transforms:  if <code class="docutils literal notranslate"><span class="pre">X</span></code> has <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/> rows,</p>
<div class="math">
<p><img src="_images/math/efe5c37bc03bf3d5826fd02dc5b43a0a51e7c271.png" alt="X[k,:] := \sum_{j=0}^{n-1} e^{-2\pi j k \sqrt{-1}/n} X[j,:],
    \qquad k=0,\ldots,n-1."/></p>
</div></dd></dl>

<dl class="py function">
<dt id="cvxopt.fftw.idft">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">idft</code><span class="sig-paren">(</span><em class="sig-param"><span class="n">X</span></em><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.idft" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense complex matrix with their inverse
discrete Fourier transforms: if <code class="docutils literal notranslate"><span class="pre">X</span></code> has <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/> rows,</p>
<div class="math">
<p><img src="_images/math/6b3d942743e5a56e5030cfaab836f542fec9019c.png" alt="X[k,:] :=
    \frac{1}{n} \sum_{j=0}^{n-1} e^{2\pi j k \sqrt{-1}/n} X[j,:],
    \qquad k=0,\ldots,n-1."/></p>
</div></dd></dl>

<p>The module also includes a discrete <em>N</em>-dimensional Fourier transform.
The input matrix is interpreted as an <em>N</em>-dimensional matrix stored
in column-major order.  The discrete <em>N</em>-dimensional Fourier transform
computes the corresponding one-dimensional transform along each dimension.
For example, the two-dimensional transform applies a one-dimensional
transform to all the columns of the matrix, followed by a one-dimensional
transform to all the rows of the matrix.</p>
<dl class="py function">
<dt id="cvxopt.fftw.dftn">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">dftn</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">dims = X.size</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.dftn" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces a dense complex matrix with its <em>N</em>-dimensional discrete
Fourier transform.  The dimensions of the <em>N</em>-dimensional matrix
are given by the <em>N</em>-tuple <code class="docutils literal notranslate"><span class="pre">dims</span></code>.  The two-dimensional transform is
computed as <code class="docutils literal notranslate"><span class="pre">dftn(X,</span> <span class="pre">X.size)</span></code>.</p>
</dd></dl>

<dl class="py function">
<dt id="cvxopt.fftw.idftn">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">idftn</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">dims = X.size</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.idftn" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces a dense complex <em>N</em>-dimensional matrix with its inverse
<em>N</em>-dimensional discrete Fourier transform.  The dimensions of the
matrix are given by the tuple <code class="docutils literal notranslate"><span class="pre">dims</span></code>. The two-dimensional inverse
transform is computed as <code class="docutils literal notranslate"><span class="pre">idftn(X,</span> <span class="pre">X.size)</span></code>.</p>
</dd></dl>

</div>
<div class="section" id="discrete-cosine-transform">
<h2>Discrete Cosine Transform<a class="headerlink" href="#discrete-cosine-transform" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.fftw.dct">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">dct</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">type = 2</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.dct" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense real matrix with their discrete
cosine transforms.  The second argument, an integer between 1 and 4,
denotes the type of transform (DCT-I, DCT-II, DCT-III, DCT-IV).
The DCT-I transform requires that the row dimension of <code class="docutils literal notranslate"><span class="pre">X</span></code> is at
least 2.  These transforms are defined as follows (for a matrix with
<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/> rows).</p>
<div class="math">
<p><img src="_images/math/2877bec99a56fcd4a3f6b39b56c2fe14acb7ee94.png" alt="\mbox{DCT-I:} \qquad
    X[k,:] &amp; := X[0,:] + (-1)^k X[n-1,:] +
        2 \sum_{j=1}^{n-2} X[j,:] \cos(\pi j k /(n-1)),
        \qquad k=0,\ldots,n-1.\\
\mbox{DCT-II:} \qquad
    X[k,:] &amp; := 2 \sum_{j=0}^{n-1} X[j,:] \cos(\pi(j+1/2)k/n),
       \qquad k=0,\ldots,n-1.\\
\mbox{DCT-III:} \qquad
    X[k,:] &amp; :=
        X[0,:] + 2 \sum_{j=1}^{n-1} X[j,:] \cos(\pi j(k+1/2)/n),
        \qquad k=0,\ldots,n-1.\\
\mbox{DCT-IV:} \qquad
    X[k,:] &amp; :=
        2 \sum_{j=0}^{n-1} X[j,:] \cos(\pi (j+1/2)(k+1/2)/n),
        \qquad k=0,\ldots,n-1."/></p>
</div></dd></dl>

<dl class="py function">
<dt id="cvxopt.fftw.idct">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">idct</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">type = 2</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.idct" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense real matrix with the inverses
of the discrete cosine transforms defined above.</p>
</dd></dl>

<p>The module also includes a discrete <em>N</em>-dimensional cosine transform.
The input matrix is interpreted as an <em>N</em>-dimensional matrix stored
in column-major order.  The discrete <em>N</em>-dimensional cosine transform
computes the corresponding one-dimensional transform along each dimension.
For example, the two-dimensional transform applies a one-dimensional
transform to all the rows of the matrix, followed by a one-dimensional
transform to all the columns of the matrix.</p>
<dl class="py function">
<dt id="cvxopt.fftw.dctn">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">dctn</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">dims = X.size</em>, <em class="sig-param">type = 2</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.dctn" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces a dense real matrix with its <em>N</em>-dimensional discrete cosine
transform. The dimensions of the <em>N</em>-dimensional matrix are given by
the <em>N</em>-tuple <code class="docutils literal notranslate"><span class="pre">dims</span></code>.  The two-dimensional transform is computed as
<code class="docutils literal notranslate"><span class="pre">dctn(X,</span> <span class="pre">X.size)</span></code>.</p>
</dd></dl>

<dl class="py function">
<dt id="cvxopt.fftw.idctn">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">idctn</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">dims = X.size</em>, <em class="sig-param">type = 2</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.idctn" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces a dense real <em>N</em>-dimensional matrix with its inverse
<em>N</em>-dimensional discrete cosine transform. The dimensions of the
matrix are given by the tuple <code class="docutils literal notranslate"><span class="pre">dims</span></code>.  The two-dimensional inverse
transform is computed as <code class="docutils literal notranslate"><span class="pre">idctn(X,</span> <span class="pre">X.size)</span></code>.</p>
</dd></dl>

</div>
<div class="section" id="discrete-sine-transform">
<h2>Discrete Sine Transform<a class="headerlink" href="#discrete-sine-transform" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.fftw.dst">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">dst</code><span class="sig-paren">(</span><em class="sig-param">X</em>, <em class="sig-param">dims</em><span class="optional">[</span>, <em class="sig-param">type = 1</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.dst" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense real matrix with their discrete
sine transforms.  The second argument, an integer between 1 and 4,
denotes the type of transform (DST-I, DST-II, DST-III, DST-IV).
These transforms are defined as follows (for a matrix with <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>
rows).</p>
<div class="math">
<p><img src="_images/math/b9f9b8057126c1f181b745e36de7f60ecbe4e41d.png" alt="\mbox{DST-I:} \qquad
    X[k,:] &amp; :=
        2 \sum_{j=0}^{n-1} X[j,:] \sin(\pi(j+1)(k+1)/(n+1)),
        \qquad k=0,\ldots,n-1.\\
\mbox{DST-II:} \qquad
    X[k,:] &amp; := 2 \sum_{j=0}^{n-1} X[j,:] \sin(\pi(j+1/2)(k+1)/n),
        \qquad k=0,\ldots,n-1.\\
\mbox{DST-III:} \qquad
    X[k,:] &amp; := (-1)^k X[n-1,:] + 2 \sum_{j=0}^{n-2}
        X[j,:] \sin(\pi(j+1)(k+1/2)/n), \qquad k=0,\ldots,n-1. \\
\mbox{DST-IV:} \qquad
    X[k,:] &amp; :=
        2 \sum_{j=0}^{n-1} X[j,:] \sin(\pi (j+1/2)(k+1/2)/n),
        \qquad k=0,\ldots,n-1."/></p>
</div></dd></dl>

<dl class="py function">
<dt id="cvxopt.fftw.idst">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">idst</code><span class="sig-paren">(</span><em class="sig-param">X</em>, <em class="sig-param">dims</em><span class="optional">[</span>, <em class="sig-param">type = 1</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.idst" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense real matrix with the inverses of the
discrete sine transforms defined above.</p>
</dd></dl>

<p>The module also includes a discrete <em>N</em>-dimensional sine transform.  The
input matrix is interpreted as an <em>N</em>-dimensional matrix stored in
column-major order.  The discrete <em>N</em>-dimensional sine transform computes
the corresponding one-dimensional transform along each dimension.  For
example, the two-dimensional transform applies a one-dimensional
transform to all the rows of the matrix, followed by a one-dimensional
transform to all the columns of the matrix.</p>
<dl class="py function">
<dt id="cvxopt.fftw.dstn">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">dstn</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">dims = X.size</em>, <em class="sig-param">type = 2</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.dstn" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces a dense real matrix with its <em>N</em>-dimensional discrete sine
transform. The dimensions of the <em>N</em>-dimensional matrix are given by
the <em>N</em>-tuple <code class="docutils literal notranslate"><span class="pre">dims</span></code>.  The two-dimensional transform is computed as
<code class="docutils literal notranslate"><span class="pre">dstn(X,</span> <span class="pre">X.size)</span></code>.</p>
</dd></dl>

<dl class="py function">
<dt id="cvxopt.fftw.idstn">
<code class="sig-prename descclassname">cvxopt.fftw.</code><code class="sig-name descname">idstn</code><span class="sig-paren">(</span><em class="sig-param">X</em><span class="optional">[</span>, <em class="sig-param">dims = X.size</em>, <em class="sig-param">type = 2</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.fftw.idstn" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces a dense real <em>N</em>-dimensional matrix with its inverse
<em>N</em>-dimensional discrete sine transform.  The dimensions of the
matrix are given by the tuple <code class="docutils literal notranslate"><span class="pre">dims</span></code>.  The two-dimensional inverse
transform is computed as <code class="docutils literal notranslate"><span class="pre">idstn(X,</span> <span class="pre">X.size)</span></code>.</p>
</dd></dl>

</div>
</div>


           </div>
           
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="spsolvers.html" class="btn btn-neutral float-right" title="Sparse Linear Equations" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="lapack.html" class="btn btn-neutral float-left" title="The LAPACK Interface" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; <a href="copyright.html">Copyright</a> 2004-2020, M.S. Andersen, J. Dahl, L. Vandenberghe
      <span class="lastupdated">
        Last updated on Apr 16, 2020.
      </span>

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
  
    <div class="footer">
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 3.0.1.
    </div>

</body>
</html>